package bm54;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/9/1 22:11
 * BM54. 三数之和
 * https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=295&tqId=731&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    /**
     * 排序 + 双指针
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>(); // 存储结果
        int n = num.length;
        if (n < 3) {
            return res;
        }
        Arrays.sort(num);
        // 每次固定一个数字
        for (int i = 0; i <= n - 3; i++) {
            // 优化
            if (num[i] > 0) {
                break; // 此时 b + c 一定不小于 0
            }
            // 去重
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }
            // 固定一个数字
            int target = -num[i]; // 另外两个数只需要满足 b + c == target == -a
            // 由于数组有序, 采用双指针划分范围
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int curSum = num[left] + num[right];
                if (curSum > target) {
                    --right;
                } else if (curSum < target) {
                    ++left;
                } else {
                    // 记录结果
                    ArrayList<Integer> curRes = new ArrayList<>();
                    curRes.add(num[i]);
                    curRes.add(num[left]);
                    curRes.add(num[right]);
                    res.add(curRes);
                    ++left;
                    --right;
                    // 去重
                    while (left < right && num[left] == num[left - 1]) {
                        ++left;
                    }
                    while (left < right && num[right] == num[right + 1]) {
                        --right;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] num = {1, 2, -2, -1};
        List<ArrayList<Integer>> arrayLists = new Solution().threeSum(num);
        System.out.println(arrayLists);
    }
}
